This invention relates to a method of compressing text data (data representing sentences, programs or the like) transmitted between computers or terminals.
An example of an existing compression method of this type is described in Nikkei Electronics, No. 403, September 8, 1986, p. 288.
FIG. 1 is a block diagram of one possible configuration of this existing data compression method, comprising a transmitting terminal 21, a compressive data coding apparatus 2 including a searching means 22, a first dictionary 23, a second dictionary 24, a modulator 25, a transmission channel 26, a demodulator 27, a decoding apparatus 20 including a searching means 28, a first dictionary 29 and a second dictionary 210 corresponding to the first and second dictionaries 23 and 24 at the transmitting end, and a receiving terminal 211. A word sent by the terminal 21 consists of several characters. The searching means 22 in the compressive data coding apparatus 2 searches the first dictionary 23 to see if it contains an entry for the input word. If it does, data corresponding to this existing entry are output. If the word cannot be found in the first dictionary 23, data corresponding to the constituent letters of the word are output from the second dictionary 24. In this way compressed data are sent via the modulator 25 to the transmission channel 26. At the receiving end, first the data are demodulated by the demodulator 27. Using the first dictionary 29 and the second dictionary 210, the searching means 28 converts the demodulated data to codes suitable for the terminal 211.
The data can be compressed most effectively if the first dictionary contains a large number of words and relatively short data "words" (i.e., each data "word" in this instance has a predetermined number of bits, each such data "word" having the same length) are assigned to each, so it is common for about 16 bits to be assigned to each word thereby providing an available 2.sup.16 (which equals 65,536) words. In the second dictionary, it is common for about 8 bits to be assigned per character (providing an available 2.sup.8 (which equals 256) characters.
Since the first dictionary 23 contains some sixty thousand words, it takes considerable time to search the first dictionary 23 for the word corresponding to the data input from the terminal 21, making it impossible for the compression process to be performed in real time at high data transmission rates. Another problem is that the dictionary requires a large memory space, hence a large amount of hardware, in which to store the large number of words.
Another example of a known compressed coding method is the adaptive Huffman method as disclosed in IEEE Transactions on Information Theory Vol. IT-24, No. 6, November 1987, pp. 668 to 674.
FIG. 2 shows the tree structure of an adaptive Huffman coding method for data words A.sub.3 to A.sub.6.
With reference to FIG. 2, the branches of the tree structure are labeled by the symbols 0 and 1, and each node except the root (r) is assigned a number in decreasing order of occurrence probability. The node numbers q.sub.1 to q.sub.10 are grouped hierarchically into sibling pairs: q.sub.1, q.sub.2 ; q.sub.3, q.sub.4 ; . . . q.sub.9, q.sub.10.
When the word A.sub.6, expressed as a combination of letters, is given as input, a compressed codeword is generated by tracing the path from the bottom node q.sub.10 linked to the word A.sub.6 to the root (r); then the occurrence count of the node number q.sub.10 is updated by being incremented by 1.
Now, the occurrence count of the sibling pair one level above the sibling pair containing the word A.sub.6 is checked and compared with the occurrence count just updated. If it is found that the size relationship has been reversed, words and occurrence counts are switched between the bottom node (q.sub.5) of the pair and node q.sub.10, then the occurrence counts of the nodes on the route from node q.sub.10 to the root node (nodes q.sub.2 and q.sub.6) are incremented by 1. The switch has the effect of switching the initially assigned compressed codes to take account of the statistical properties of the transmitted data.
In adaptive Huffman coding, an increase in the number of words (bottom nodes) generally causes an exponential increase in the number of tree branches, so considerable hardware is required and it takes time to find the bottom node and generate the codeword by tracing the tree structure.